第6章 整数集合

Huan Lee Lv5
  2023-08-24 14:37:32 2023-08-24 14:37:32 Created   2024-02-26 04:53:15 2024-02-26 04:53:15 Updated      

整数集合(intset)是集合键的底层实现之一, 当一个集合只包含整数值元素, 并且这个集合的元素数量不多时, 则使用整数集合作为底层实现.

整数集合的保存类型为int16_t, int32_t, int64_t的整型, 集合中不会有重复元素.

6.1 整数集合的实现

Untitled

  • contents的采用int8_t作为底层实现, 但是整数集合中保存数据的实际类型取决于encoding
  • encoding的取值为INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64

6.2 升级

每当我们要将一个新元素添加到整数集合中, 且新元素的类型比集合现有所有元素的类型都要长时, 整数集合需要先进行升级, 才能完成添加. 具体步骤分三步:

  1. 根据新元素的类型, 扩展整数集合底层数组的空间大小, 并为新元素分配空间

  2. 将底层数组现有的所有元素替换成新元素相同的类型, 并将转换后的元素放置到正确的位上.

  3. 将新元素添加到底层数组中

假设现在要将int32_t的整数值添加到int16_t的整数集合中:

Untitled

Untitled

在原有底层数组的基础上扩展空间

Untitled

从后往前移动旧元素

Untitled

添加新元素. (新元素只会出现在底层数组的最开头或者最末尾)

6.3 升级的好处

  1. 提升整数集合的灵活性: 可以随意添加不同类型地整型, 不必担心类型错误. (适配其他语言)

  2. 尽可能地节约内存

6.4 降级

省流: 不支持捏

6.5 整数集合API

Untitled

  • Title: 第6章 整数集合
  • Author: Huan Lee
  • Created at : 2023-08-24 14:37:32
  • Updated at : 2024-02-26 04:53:15
  • Link: https://www.mirthfullee.com/2023/08/24/notion-第6章 整数集合-6dbc8af8/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
第6章 整数集合
  1. 6.1 整数集合的实现
  2. 6.2 升级
  3. 6.3 升级的好处
  4. 6.4 降级
  5. 6.5 整数集合API